package com.wyp168.leetcode.treenode;

/**
 * @ClassName ConstructMaximumBinaryTree
 * @Description TODO 给定一个不重复元素的整型数组，返回一个最大二叉树
 * @Author wyp168
 * @Date 2022/8/20 03:06
 */
public class ConstructMaximumBinaryTree {
    public static void main(String[] args) {
        ConstructMaximumBinaryTree constructMaximumBinaryTree = new ConstructMaximumBinaryTree();
        int[] nums = {3,2,1,6,0,5};
        TreeNode treeNode = constructMaximumBinaryTree.constructMaximumBinaryTree(nums);
        System.out.println(treeNode);
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructChildNode(nums, 0, nums.length - 1);

    }

    public  TreeNode constructChildNode(int[] nums, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            return new TreeNode(nums[startIndex]);
        }
        //找出传入数组中的最大值，以最大值进行分割
        int max = nums[startIndex];
        int maxIndex = startIndex;
        for (int i = startIndex; i <= endIndex; i++) {
            if (max < nums[i]) {
                maxIndex = i;
                max = nums[i];
            }
        }
         if (maxIndex ==  startIndex) {
            TreeNode node = new TreeNode(max);
            node.right = constructChildNode(nums, startIndex + 1, endIndex);
            return node;
        } else if (maxIndex == endIndex){
            TreeNode node = new TreeNode(max);
            node.left = constructChildNode(nums, startIndex, maxIndex - 1);
            return node;
        } else if (startIndex < maxIndex && maxIndex < endIndex){
             TreeNode node = new TreeNode(max);
             node.left = constructChildNode(nums, startIndex, maxIndex - 1);
             node.right = constructChildNode(nums, maxIndex + 1, endIndex);
             return node;
         } else {
             return null;
         }
    }
}
